package com.cat.dynamicPlanning02;

import java.util.Arrays;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/maximum-profit-in-job-scheduling/
 * @create 2025/10/18 16:42
 * @since JDK17
 */

public class Solution25 {
    static int N = ((int) (5e4 + 10));
    static int[][] jobs = new int[N][3];
    static int[] dp = new int[N];
    int find(int r, int start) {
        int l = -1, mid;
        while (l + 1 < r) {
            mid = l + r >> 1;
            if (jobs[mid][1] <= start) {
                l = mid;
            } else {
                r = mid;
            }
        }
        return l;
    }

    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        for (int i = 0; i < n; i++) {
            jobs[i][0] = startTime[i];
            jobs[i][1] = endTime[i];
            jobs[i][2] = profit[i];
        }
        Arrays.sort(jobs, 0, n, (a, b) -> (a[1] - b[1]));
        dp[0] = jobs[0][2];
        for (int i = 1; i < n; i++) {
            int start = jobs[i][0];
            dp[i] = jobs[i][2];
            if (jobs[0][1] <= start) {   // 一定可以多做几个活动
                dp[i] += dp[find(i, start)];
            }
            dp[i] = Math.max(dp[i - 1], dp[i]);
        }

        return dp[n - 1];
    }
}
